Network communications often require classifying information units, such as packets, that are transported between various network devices (e.g., routers, switches, terminals, etc.) For example, packets may be examined and classified to support various applications, such as network partitioning, group mobility tracking, security control and enforcement, quality of service support, and so on. In particular, a network component may examine and classify incoming packets using classification rules to determine an action that should be applied to a packet, such as whether the packet should be dropped, transmitted to its destination, re-routed, modified, quarantined, etc. Due to the complexity and customizability of such rules, the classification process is typically implemented as a software application. However, performance of such an application is often slowed by limited processing power of a central processing unit (CPU) running the application and expanded complexity of the application caused by the flexible nature of the classification rules.
To improve on the slow performance, constraints on the complexity of the rules are often enforced. For example, the rules may be limited to a set that that could be easily organized into a binary search tree. However, due to the exact match constraint, rules of sufficient complexity have to be organized in multiple trees rather than a single tree. Because searching multiple trees is significantly slower than searching the single tree, the optimizing advantage of using a binary search tree is compromised.
Another common approach is to employ hash tables, which involves transforming the look-up keys of the classification rules into a statistically favorable hash index associated with the location of the actual rule. While hash tables are easy to implement, due to the exact match constraint multiple passes across different tables are required to implement the desired classification capability. Furthermore, a successful match is not guaranteed even if one does exist.